extends Node
class_name GraphFindPath

var graph = {}  # 用于存储节点的字典，节点名称作为键，节点对象作为值

# 添加一个节点到图中
func add_vector(v):
	graph[v] = {}

# 添加一个有权重的边
func add_link(v1:Vector2, v2:Vector2):
	if v1 not in graph:
		add_vector(v1)
	if v2 not in graph:
		add_vector(v2)
	var weight=v1.distance_to(v2)
	graph[v1][v2] = weight
	graph[v2][v1] = weight

# 获取两个节点之间的权重
func get_edge_weight(v1, v2):
	if v1 in graph and v2 in graph and v2 in graph[v1]:
		return graph[v1][v2]
	return null  # 如果没有找到边，则返回 null

var activePoints = []  # 存储路径中的活动点
var startPoint:Vector2
var endPoint:Vector2

func set_graph(三角形集:Array):
	for 三角形 in 三角形集:
		add_link(三角形[0],三角形[1])
		add_link(三角形[1],三角形[2])
		add_link(三角形[0],三角形[2])
	
func find_path(start:Vector2, end:Vector2):
	var openSet:Array= [start]
	var cameFrom:Dictionary = {}
	var gScore:Dictionary= {}
	for vector in graph:
		gScore[vector]=INF
	gScore[start] = 0

	while openSet.size() > 0:
		var current = get_lowest_gScore(openSet, gScore)
		if current == end:
			return reconstruct_path(cameFrom, current)

		openSet.erase(current)

		for neighbor in graph[current].keys():
			var tentative_gScore = gScore[current] + graph[current][neighbor]

			if tentative_gScore < gScore[neighbor]:
				cameFrom[neighbor] = current
				gScore[neighbor] = tentative_gScore
				if not openSet.has(neighbor):
					openSet.append(neighbor)
	return []

func get_lowest_gScore(openSet, gScore):
	var lowest_gScore = INF
	var lowest_vector = null
	for vector in openSet:
		if gScore[vector] < lowest_gScore:
			lowest_gScore = gScore[vector]
			lowest_vector = vector
	return lowest_vector

func reconstruct_path(cameFrom, current):
	var totalPath = [current]
	while cameFrom.has(current):
		current = cameFrom[current]
		totalPath.append(current)
	return totalPath

func remove_vector(vector):
	if graph.has(vector):
		for key in graph[vector].keys():
			graph[key].erase(vector)
		graph.erase(vector)
